/**
 * Project Name:javaBaseReview
 * Package Name:com.xuwei.base.graph
 * author:David
 * Date:2015年8月22日上午10:17:20
 * Copyright (c) 2015, xw123box@126.com All Rights Reserved.
 *
 */
package com.xuwei.base.graph;

import org.junit.Test;

/**
 * @author David
 * @since 2015年8月22日 上午10:17:20
 * @version 
 * @since JDK 1.6
 */
public class GraphTest {
	
	@Test
	public void testUndirectGraph() {
		UndirectedGraph uGraph=(UndirectedGraph) createUndiGraph();
		Iterator iterator=uGraph.getVertex();
		Vertex v=(Vertex) (iterator.first().getData());
		System.out.println("=========深度优先遍历无向图======");
		Iterator it=uGraph.DFSTraverse(v);
		for(it.first();!it.isDone();it.next()){
			Vertex vertx=(Vertex) it.currentItem();
			System.out.println("visited:"+vertx.isVisited()+" "+vertx.getInfo());
		}
		
		System.out.println("=========广度优先遍历无向图======");
		Iterator it2=uGraph.BFSTraverse(v);
		for(it2.first();!it2.isDone();it2.next()){
			Vertex vertx=(Vertex) it2.currentItem();
			System.out.println("visited:"+vertx.isVisited()+" "+vertx.getInfo());
		}
	
	}


	public static Graph createUndiGraph() {
		UndirectedGraph udGraph=new UndirectedGraph();
		//建四个顶点
		Vertex vertex1=new Vertex(udGraph, "v1");
		Vertex vertex2=new Vertex(udGraph, "v2");
		Vertex vertex3=new Vertex(udGraph, "v3");
		Vertex vertex4=new Vertex(udGraph, "v4");
			
		//建四条无向边
		new Edge(udGraph, vertex1, vertex2, "(v1-v2)");
		new Edge(udGraph, vertex1, vertex3, "(v1-v3)", 2);
		new Edge(udGraph, vertex1, vertex4, "(v1-v4)", 6);
		new Edge(udGraph, vertex3, vertex4, "(v3-v4)");
		
		return udGraph;
	} 

	
	@Test
	public void testCreateLinkList(){
		LinkListDLNode list=new LinkListDLNode();
		for(int i=0;i<5;i++){
			list.insertLast(i+1);
//			list.insertFirst(i+1);
		}
		
		int size=list.getSize();
		System.out.println(size);
		System.out.println("isEmpty:"+list.isEmpty());
		System.out.println("first node:"+list.first().getData());
		System.out.println("last node:"+list.last().getData());
		
		list.printLink();
	}
	
	@Test
	public void testCreateUndirectGraph(){
		System.out.println("=======无向图创建开始========");
		UndirectedGraph udGraph=new UndirectedGraph();
		//建四个顶点
		Vertex vertex1=new Vertex(udGraph, "v1");
		Vertex vertex2=new Vertex(udGraph, "v2");
		Vertex vertex3=new Vertex(udGraph, "v3");
		Vertex vertex4=new Vertex(udGraph, "v4");
			
		
		//建四条无向边
		new Edge(udGraph, vertex1, vertex2, "(v1-v2)");
		new Edge(udGraph, vertex1, vertex3, "(v1-v3)", 8);
		new Edge(udGraph, vertex1, vertex4, "(v1-v4)");
		new Edge(udGraph, vertex3, vertex4, "(v3-v4)");
		
		System.out.print("顶点数："+udGraph.getVexNum()+", ");
		System.out.println("边数："+udGraph.getEdgeNum());
		
//		遍历顶点集合
		System.out.println("-----遍历顶点表-----");
		Iterator iterator=udGraph.getVertex();
		do{
			Vertex v=(Vertex)iterator.currentItem();
			System.out.print(v.getInfo()+"->");
		}while(iterator.next()!=null);
		System.out.println("end");
		
		
//		遍历边表集合
		System.out.println("-----遍历边表------");
		Iterator iterator2=udGraph.getEdge();
		do{
			Edge e=(Edge)iterator2.currentItem();
			System.out.print(e.getInfo()+"["+e.getWeight()+"]->");
		}while(iterator2.next()!=null);
		System.out.println("end");
		
		System.out.println("=======无向图创建结束========");
	}
	
	@Test
	public void testRemoveVertexOper(){
		UndirectedGraph uGraph=(UndirectedGraph) createUndiGraph();
		Iterator it=uGraph.getVertex();
		printVertexs(it);
		printEdges(uGraph.getEdge());
		
		Vertex firstV = (Vertex)it.first().getData();
		System.out.println(firstV.getInfo());
		uGraph.remove(firstV);
		printVertexs(it);
		printEdges(uGraph.getEdge());
	}
	
	@Test
	public void testRemoveEdgeOper(){
		UndirectedGraph uGraph=(UndirectedGraph) createUndiGraph();
		Iterator it=uGraph.getEdge();
		printEdges(it);
		
		Edge firstE = (Edge)it.first().getData();
		System.out.println(firstE.getInfo());
		uGraph.remove(firstE);
		printEdges(it);
	}


	private void printEdges(Iterator it) {
		for(it.first();!it.isDone();it.next()){
			Edge e = (Edge)it.currentItem();
			System.out.print(e.getInfo()+"["+e.getWeight()+"]"+", ");
		}
		System.out.println("end");
	}
	
	private void printVertexs(Iterator it) {
		for(it.first();!it.isDone();it.next()){
			Vertex v = (Vertex)it.currentItem();
			System.out.print(v.getInfo()+", ");
		}
		System.out.println("end");
	}
	
	@Test
	public void testEdgeFromTo(){
		UndirectedGraph uGraph=(UndirectedGraph) createUndiGraph();
		Vertex v1 = (Vertex)uGraph.getVertex().getItem(0);
		Vertex v2 = (Vertex)uGraph.getVertex().getItem(1);
		Vertex v3 = (Vertex)uGraph.getVertex().getItem(2);
		Vertex v4 = (Vertex)uGraph.getVertex().getItem(3);
		System.out.println(v4.getInfo());
		System.out.println(uGraph.edgeFromTo(v4, v1).getInfo());
	}
	
	@Test
	public void testMinSpanTree(){
		UndirectedGraph udGraph= createUndiGraph2();
		udGraph.generateMST();
		//打印最小生成树的边
		System.out.println("最小生成树mst边：");
		Iterator mstEdges = udGraph.getEdge();
		for(mstEdges.first();!mstEdges.isDone();mstEdges.next()){
			Edge edge = (Edge) mstEdges.currentItem();
			if(edge.isMSTEdge()){
				System.out.print(edge.toString().concat(","));
			}
		}
		System.out.println("end");
	}
	
	@Test
	public void testAdjVertexs(){
		UndirectedGraph udGraph= createUndiGraph2();
		Vertex vb = (Vertex)udGraph.getVertex().getItem(0);
		System.out.println(vb.getInfo());
		Iterator vadj = udGraph.adjVertexs(vb);
		for(vadj.first();!vadj.isDone();vadj.next()){
			Vertex _v = (Vertex) vadj.currentItem();
			System.out.println(_v.getInfo());
		}
	}
	
	
	public UndirectedGraph createUndiGraph2(){
		System.out.println("==============无向图创建开始========================================");
		UndirectedGraph udGraph=new UndirectedGraph();
		//建四个顶点
		Vertex a=new Vertex(udGraph, "a");
		Vertex b=new Vertex(udGraph, "b");
		Vertex c=new Vertex(udGraph, "c");
		Vertex d=new Vertex(udGraph, "d");
		Vertex e=new Vertex(udGraph, "e");
		Vertex f=new Vertex(udGraph, "f");
		Vertex g=new Vertex(udGraph, "g");
		Vertex h=new Vertex(udGraph, "h");
		Vertex i=new Vertex(udGraph, "i");
		
		//建四条无向边
		new Edge(udGraph, a, b, "(a, b)", 4);
		new Edge(udGraph, a, h, "(a, h)", 8);
		new Edge(udGraph, b, c, "(b, c)", 8);
		new Edge(udGraph, b, h, "(b, h)", 11);
		new Edge(udGraph, c, d, "(c, d)", 7);
		new Edge(udGraph, c, f, "(c, f)", 4);
		new Edge(udGraph, c, i, "(c, i)", 2);
		new Edge(udGraph, d, e, "(d, e)", 9);
		new Edge(udGraph, d, f, "(d, f)", 14);
		new Edge(udGraph, e, f, "(e, f)", 10);
		new Edge(udGraph, f, g, "(f, g)", 2);
		new Edge(udGraph, g, i, "(g, i)", 6);
		new Edge(udGraph, g, h, "(g, h)", 1);
		new Edge(udGraph, h, i, "(h, i)", 7);
		
		System.out.print("顶点数："+udGraph.getVexNum()+", ");
		System.out.println("边数："+udGraph.getEdgeNum());
		
//		遍历顶点集合
		System.out.println("-----遍历顶点表-----");
		Iterator iterator=udGraph.getVertex();
		do{
			Vertex v=(Vertex)iterator.currentItem();
			System.out.print(v.getInfo()+"->");
		}while(iterator.next()!=null);
		System.out.println("end");
		
		
//		遍历边表集合
		System.out.println("-----遍历边表------");
		Iterator iterator2=udGraph.getEdge();
		do{
			Edge edge=(Edge)iterator2.currentItem();
			System.out.print(edge.getInfo()+"["+edge.getWeight()+"]->");
		}while(iterator2.next()!=null);
		System.out.println("end");
		
		System.out.println("==============无向图创建结束========================================");
		return udGraph;
	}
	
	public static Graph createDirectGraph() {
		DirectGraph graph=new DirectGraph();
		//建四个顶点
		Vertex a=new Vertex(graph, "a");
		Vertex b=new Vertex(graph, "b");
		Vertex c=new Vertex(graph, "c");
		Vertex d=new Vertex(graph, "d");
		Vertex e=new Vertex(graph, "e");
		Vertex f=new Vertex(graph, "f");
		Vertex g=new Vertex(graph, "g");
		Vertex h=new Vertex(graph, "h");
		Vertex i=new Vertex(graph, "i");
			
		//建四条无向边
		new Edge(graph, a, b, "<a-b>",4);
		new Edge(graph, b, c, "<b-c>",8);
		new Edge(graph, c, d, "<c,d>");
		return graph;
	} 
	
	@Test
	public void testGetShortestPath(){
		DirectGraph graph=new DirectGraph();
		Vertex a = new Vertex(graph, "a");
		Vertex b = new Vertex(graph, "b");
		Vertex c = new Vertex(graph, "c");
		Vertex d = new Vertex(graph, "d");
		Vertex e = new Vertex(graph, "e");
		
		new Edge(graph, a, b, "<a, b>", 10);
		new Edge(graph, a, c, "<a, c>", 3);
		new Edge(graph, b, c, "<b, c>", 1);
		new Edge(graph, b, d, "<b, d>", 2);
		new Edge(graph, c, b, "<c, b>", 4);
		new Edge(graph, c, d, "<c, d>", 8);
		new Edge(graph, c, e, "<c, e>", 2);
		new Edge(graph, d, e, "<d, e>", 7);
		new Edge(graph, e, d, "<e, d>", 9);
		
		Vertex vb = (Vertex)graph.getVertex().getItem(0);
		System.out.println(vb.getInfo());
		
		printVertexs(graph.getVertex());
		printEdges(graph.getEdge());
		
		Iterator pathIt  = graph.shortestPath(vb);
		System.out.println("=======最短路径==============");
		for(pathIt.first();!pathIt.isDone();pathIt.next()){
			Path path = (Path) pathIt.currentItem();
			System.out.print("("+path.getEnd().getInfo()+","+path.getDistance()+"){");
			Iterator pathInfo = path.getPathInfo().elements();
			for(pathInfo.first();!pathInfo.isDone();pathInfo.next()){
				Vertex _v = (Vertex)(pathInfo.currentItem());
				System.out.print(_v.getInfo());
			}
			System.out.print("},");
		}
		System.out.println("end");
	}
	
	
	@Test
	public void testTopSort(){
		DirectGraph graph=new DirectGraph();
		Vertex a = new Vertex(graph, "a");
		Vertex b = new Vertex(graph, "b");
		Vertex c = new Vertex(graph, "c");
		Vertex d = new Vertex(graph, "d");
		Vertex e = new Vertex(graph, "e");
		Vertex f = new Vertex(graph, "f");
		
		new Edge(graph, a, b, "<a, b>");
		new Edge(graph, a, d, "<a, d>");
		new Edge(graph, b, f, "<b, f>");
		new Edge(graph, c, b, "<c, b>");
		new Edge(graph, c, f, "<c, f>");
		new Edge(graph, e, a, "<e, a>");
		new Edge(graph, e, b, "<e, b>");
		new Edge(graph, e, f, "<e, f>");
		
		printVertexs(graph.getVertex());
		printEdges(graph.getEdge());
		System.out.println("=======拓扑排序====================");
		Iterator topIt = graph.toplogicalSort();
		for(topIt.first();!topIt.isDone();topIt.next()){
			Vertex vertex = (Vertex) topIt.currentItem();
			System.out.print(vertex.getInfo()+",");
		}
		System.out.println("end");
		
	}
}






